SP8222 NSUBSTR - Substrings

不难发现到$f[i]$就是长度为 $i$ 子串的 $|endpos|$ 的最大值。

根据一个性质后缀自动机的一个点的 $endpos$ 被他的后继分为了很多部分，所以我们可以用$\text{parent树dp}$，处理出它的$|endpos|$。

接着是统计答案，显然我们可以用线段树覆盖。

但是，我们并不需要将对于每个点$u$将 $Minlen[u]$ 到 $Maxlen[u]$ 更新一遍，而是只更新$Maxlen[u]$，最后循环倒着处理。（因为一个字符串如果包含最长的字串有$|endpos(u)|$次，那么它包含更短的子串肯定有$|endpos(u)|$次）

这样就可以$\Theta(n)$解决了。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 250000 , MAXK = 26;
struct Suffix_Automaton {
	int Root , Size , Last , len , Maxlen[ 2 * MAXN + 5 ]; 
	int Trans[ 2 * MAXN + 5 ][ MAXK + 5 ] , Link[ 2 * MAXN + 5 ];
	long long dp[ 2 * MAXN + 5 ] , Tag[ 2 * MAXN + 5 ];
	
	Suffix_Automaton( ) { Root = Size = Last = 1; }
	
	void Copy( int u , int v ) {
		for( int i = 1 ; i <= MAXK ; i ++ )
			Trans[ u ][ i ] = Trans[ v ][ i ];
	}
	void Extend( int chr ) {
		int Newnode = ++ Size , u = Last;
		Maxlen[ Newnode ] = Maxlen[ u ] + 1; dp[ Newnode ] = 1;
		
		for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
			Trans[ u ][ chr ] = Newnode;
		
		if( !u ) Link[ Newnode ] = 1;
		else {
			int v = Trans[ u ][ chr ];
			
			if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
			else {
				int w = ++ Size;
				Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
				for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
				Link[ w ] = Link[ v ];
				Link[ v ] = Link[ Newnode ] = w;	
			}
		}
		Last = Newnode;
	}
	void Build( char *str ) {
		len = strlen( str );
		for( int i = 0 ; i < len ; i ++ )
			Extend( str[ i ] - 'a' + 1 );
		Sort( );
	}
	
	int tot[ 2 * MAXN + 5 ] , Topu[ 2 * MAXN + 5 ];
	void Sort( ) {
		for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
		for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
		for( int i = 1 ; i <= Size ; i ++ ) Topu[ tot[ Maxlen[ i ] ] -- ] = i; 
	} 
	
	void Dp( ) {
		for( int i = Size ; i >= 1 ; i -- ) {
			int u = Topu[ i ];
			dp[ Link[ u ] ] += dp[ u ]; 
			Tag[ Maxlen[ u ] ] = max( Tag[ Maxlen[ u ] ] , dp[ u ] );
		}
	}
	void Work( ) {
		for( int i = len ; i >= 1 ; i -- ) Tag[ i ] = max( Tag[ i ] , Tag[ i + 1 ] );
		for( int i = 1 ; i <= len ; i ++ ) printf("%d\n",Tag[ i ]);
	}
}SAM;

char str[ MAXN + 5 ];

int main( ) {
	scanf("%s", str ); 
	SAM.Build( str ); SAM.Dp( );
	SAM.Work();
	return 0;
}